1. Field of the Invention
The present invention relates to the processing of digital data to effect variable-length encoding.
2. Description of Related Art
Variable-length coding (VLC) commands a dominant role in data compression as a result of its speed and simplicity. However, the very trends that commend its employ--the growth in data volume and increasing transmission rates--have preponderated to threaten its ability to palliate them. The art of VLC encoding has therefore focused on speed, yet with deference to circuit size.
A mapping between fixed-length input data, termed symbols, and variable-length output data, termed codewords, constitutes a codetable. The codetable singularly determines most of the structure, and consequently most of the performance characteristics, of an encoder. This codetable usually takes one of two forms: a compact tree-based arrangement or a larger direct tabulation. The tree-based arrangement was originally a decoding device, but has recently been transferred to the encoding domain. In support of decoding, its attributes are highly desirable. By contrast, the arrangement proves awkward with encoding. Much of the art has therefore attempted to reconcile it with encoding. This endeavor has met with only limited success. Some art mitigates the size advantage the arrangement suggests over direct tabulation. Other art requires post-encoding reversal operations that introduce undesirable variable latency between the output of the primary encoder and output of post-encoding hardware.
Direct tabulation, by virtue of its directness, should be fast. It is often not as compact as desired, though. Because codewords are variable in length, indication of the length of each codeword is required. This may be accomplished in a number of ways, all of which necessitate some concessions. For example, length may be stored explicitly alongside codewords, as an associated value of each symbol. This obviously consumes precious memory space. Alternatively, codewords of equal length may be grouped, with length and associated memory ranges specified separately. This approach restricts the type of code to which the encoder applies, e.g., the Huffinan-Shannon-Fano code would be supported, but general Huffinan codes would not. It also results in complex--and hence slow--processing.
Note that any scheme that explicitly stores a length value in any manner must employ arithmetic operations in releasing the recalled codeword to the output. Most often a unit decrement operation is utilized, reducing the length by one each time a bit of the codeword is output. Such an operation, while intrinsically simple, is often responsible for over half of the delay in a processing cycle.